package leetcode.dp;

import java.util.Scanner;

/**
 * leetCode 32
 * 最长有效括号
 * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度
 * 思路：需用到辅助数组d[s.length()]，表示从当前字符开始，到字符串结尾的最长有效括号子串长度（当前字符需为有效括号子串的第一个字符）

 解题思路：从字符串结尾往前处理，求辅助数组d[]

 当前字符下标为index，若当前字符为左括号'('，判断index+1+d[index+1]位置的字符是否为右括号')'，若为右括号，则d[index] = d[index+1]+2，并且判断index+1+d[index+1]+1位置的元素是否存在，若存在，则d[index] += d[index+1+d[index+1]+1]（解决上述两个有效括号子串直接相邻的情况）

 */
public class Dp32 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            new Dp32().longestValidParentheses(str);
        }
    }
    public int longestValidParentheses(String s) {
        int [] dp = new int[s.length()];
        // 子串长度为1和为2的初始化
        for(int i = s.length() - 2; i >= 0; i --){
            int symIndex = i+1+dp[i+1];
            if(s.charAt(i) == '(' && symIndex < s.length() && s.charAt(symIndex) == ')'){
                dp[i] = dp[i + 1] + 2;
                if(symIndex + 1 < s.length()){
                    // 有效括号不相连的情况
                    dp[i] += dp[symIndex + 1];
                }
            }
        }
        int max = 0;
        for(int i = 0; i < s.length(); i ++){
            if(max< dp[i]) max = dp[i];
        }
        return max;
    }
}
